The design of hardware devices and systems that involve memory access, such as microprocessor-based systems, is often tested and verified by simulation. Typically, a simulated model of the design is subjected to multiple test cases generated by a test generator. In some cases, memory initialization is performed as part of the test case generation process. Several methods and systems for performing memory allocation in test case generation are known in the art.
For example, U.S. Pat. No. 6,845,440 describes a system for detecting and/or avoiding memory usage conflicts when generating and merging multi-threaded software test cases. Initially, a test case generator is given a unique segment of memory which it can use. A plurality of test cases are generated, one at a time, by the test case generator. When the first test case is generated, the memory segment used is noted. When each of the subsequent test cases is generated, a memory segment of the same size as the first test case, but not overlapping that of the previously-assigned test cases, is assigned to each subsequent test case.
Another memory allocation method is described by Chandra et al., in “AVPGEN—A Test Generator for Architecture Verification,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, (3:2), June, 1995, pages 188-200. In AVPGEN, a memory allocator is invoked for allocating memory under certain constraints for decoded instructions. The memory allocator is invoked sequentially, as instructions are being decoded.
Many tasks that are addressed by decision-making systems and artificial intelligence can be framed as constraint satisfaction problems (CSPs). Generally, when expressing a problem as a CSP, the problem is specified in terms of a set of variables, each of which can assume values in a given domain, and a set of predicates, or constraints, that the variables should simultaneously satisfy. The set of variables and constraints is referred to as a constraint network. Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. A solution to the problem is an assignment of a value to each variable from its domain that satisfies all of the constraints.
Several CSP solving methods and tools are known in the art. For example, a number of common solving techniques are described by Kumar in “Algorithms for Constraint Satisfaction Problems: A Survey,” Artificial Intelligence Magazine, 13:1 (1992), pages 32-44.
Automatic test generation is sometimes performed using constraint satisfaction methods. The use of CSP in automated generation of test programs is described, for example, by Bin et al. in “Using Constraint Satisfaction Formulation and Solution Techniques for Random Test Program Generation,” IBM Systems Journal, (41:3), 2002, pages 386-402. The paper shows methods for modeling random test program generation as a CSP, and describes a set of solution techniques that are used in practical test-case generation tools.
As another example, Adir et al., describe a test generator that uses a dedicated CSP solver in “Piparazzi: A Test Program Generator for Micro-architecture Flow Verification,” Eighth IEEE International High-Level Design Validation and Test Workshop (Nov. 12-14, 2003), pages 23-28. The test generator converts user requests for micro-architectural events into test programs.